<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang>
<head><meta name="generator" content="Hexo 3.8.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/hcigmoid/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">




  
  
  
  

  
    
    
  

  
    
      
    

    
  

  

  

  

  
    
    
    <link href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic|Lato:300,300italic,400,400italic,700,700italic&subset=latin,latin-ext" rel="stylesheet" type="text/css">
  






<link href="/hcigmoid/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/hcigmoid/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/hcigmoid/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/hcigmoid/images/favicon-32x32-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/hcigmoid/images/favicon-16x16-next.png?v=5.1.4">


  <link rel="mask-icon" href="/hcigmoid/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="Hexo, NexT">





  <link rel="alternate" href="/hcigmoid/atom.xml" title="HCigmoid" type="application/atom+xml">






<meta name="description" content="总结心得">
<meta name="keywords" content="feature, model, algorithm">
<meta property="og:type" content="website">
<meta property="og:title" content="HCigmoid">
<meta property="og:url" content="http://guyuecanhui.gitee.io/hcigmoid/page/6/index.html">
<meta property="og:site_name" content="HCigmoid">
<meta property="og:description" content="总结心得">
<meta property="og:locale" content="default">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="HCigmoid">
<meta name="twitter:description" content="总结心得">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/hcigmoid/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://guyuecanhui.gitee.io/hcigmoid/page/6/">





  <title>HCigmoid</title>
  








</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="default">

  
  
    
  

  <div class="container sidebar-position-left 
  page-home">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/hcigmoid/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">HCigmoid</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">Watch, learn and practise</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/hcigmoid/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/hcigmoid/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br>
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/hcigmoid/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/hcigmoid/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/hcigmoid/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            归档
          </a>
        </li>
      

      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br>
            
            搜索
          </a>
        </li>
      
    </ul>
  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocomplete="off" placeholder="搜索..." spellcheck="false" type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            
  <section id="posts" class="posts-expand">
    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://guyuecanhui.gitee.io/hcigmoid/hcigmoid/2019/02/10/confidence-interval/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="古月残辉">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/hcigmoid/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="HCigmoid">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hcigmoid/2019/02/10/confidence-interval/" itemprop="url">置信区间在推荐中的应用</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2019-02-10T13:22:05+08:00">
                2019-02-10
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/hcigmoid/categories/推荐系统/" itemprop="url" rel="index">
                    <span itemprop="name">推荐系统</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/hcigmoid/2019/02/10/confidence-interval/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/hcigmoid/2019/02/10/confidence-interval/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          

          

          
            <div class="post-wordcount">
              
                
                <span class="post-meta-item-icon">
                  <i class="fa fa-file-word-o"></i>
                </span>
                
                  <span class="post-meta-item-text">字数统计&#58;</span>
                
                <span title="字数统计">
                  1.6k
                </span>
              

              
                <span class="post-meta-divider">|</span>
              

              
                <span class="post-meta-item-icon">
                  <i class="fa fa-clock-o"></i>
                </span>
                
                  <span class="post-meta-item-text">阅读时长 &asymp;</span>
                
                <span title="阅读时长">
                  5
                </span>
              
            </div>
          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          <p>学过统计的同学都对置信区间的概念非常熟悉，实际上，离开置信区间谈统计值没啥意义，或者说经常会造成很大的误导。简单来讲，置信区间是指基于观测样本来估计一个未知参数（如均值）时，我们相当确定（用置信度来度量）参数可能的取值范围。如果不考虑置信区间的概念，在我们观察到有 2 个用户喜欢一个视频、1 个用户不喜欢一个视频时，会估计该视频的推荐度为 66%，而认为它是一个高质量的视频，如果一旦将它进行大规模推荐时，很可能发现这个视频的实际转化率低的可怜。</p>
<p>因此在推荐里，置信区间是需要密切关注的概念。在推荐领域实践中，我从 3 个简单的算法来分别介绍置信区间的应用。</p>
          <!--noindex-->
          <div class="post-button text-center">
            <a class="btn" href="/hcigmoid/2019/02/10/confidence-interval/#more" rel="contents">
              阅读全文 &raquo;
            </a>
          </div>
          <!--/noindex-->
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://guyuecanhui.gitee.io/hcigmoid/hcigmoid/2018/10/04/ffm/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="古月残辉">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/hcigmoid/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="HCigmoid">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hcigmoid/2018/10/04/ffm/" itemprop="url">特征组合之FFM</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2018-10-04T14:43:50+08:00">
                2018-10-04
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/hcigmoid/categories/推荐系统/" itemprop="url" rel="index">
                    <span itemprop="name">推荐系统</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/hcigmoid/2018/10/04/ffm/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/hcigmoid/2018/10/04/ffm/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          

          

          
            <div class="post-wordcount">
              
                
                <span class="post-meta-item-icon">
                  <i class="fa fa-file-word-o"></i>
                </span>
                
                  <span class="post-meta-item-text">字数统计&#58;</span>
                
                <span title="字数统计">
                  2k
                </span>
              

              
                <span class="post-meta-divider">|</span>
              

              
                <span class="post-meta-item-icon">
                  <i class="fa fa-clock-o"></i>
                </span>
                
                  <span class="post-meta-item-text">阅读时长 &asymp;</span>
                
                <span title="阅读时长">
                  8
                </span>
              
            </div>
          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          <p>前段时间搞 LR 的特征优化，切身体会到人工特征工程实在太费劲了，一方面发掘高价值的特征十分困难，另一方面某些特征之间需要组合才能有效，比如用户对视频的某个特征的偏好，就必须将视频的特征和用户的特征进行组合。LR 是线性模型，没法自动做特征组合，只能人工搞，但人工来干这事就相当麻烦了。自然而然的，就会想到用可以自动组合特征的模型。现在了解的包括 FM、FFM 等基于矩阵分解的模型、基于 GBDT 之类的树模型和基于 DNN 的网络模型。这篇文章先介绍下 FFM 模型。</p>
          <!--noindex-->
          <div class="post-button text-center">
            <a class="btn" href="/hcigmoid/2018/10/04/ffm/#more" rel="contents">
              阅读全文 &raquo;
            </a>
          </div>
          <!--/noindex-->
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://guyuecanhui.gitee.io/hcigmoid/hcigmoid/2018/10/04/ffm 2/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="古月残辉">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/hcigmoid/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="HCigmoid">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hcigmoid/2018/10/04/ffm 2/" itemprop="url">特征组合之FFM</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2018-10-04T14:43:50+08:00">
                2018-10-04
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/hcigmoid/categories/推荐系统/" itemprop="url" rel="index">
                    <span itemprop="name">推荐系统</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/hcigmoid/2018/10/04/ffm 2/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/hcigmoid/2018/10/04/ffm 2/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          

          

          
            <div class="post-wordcount">
              
                
                <span class="post-meta-item-icon">
                  <i class="fa fa-file-word-o"></i>
                </span>
                
                  <span class="post-meta-item-text">字数统计&#58;</span>
                
                <span title="字数统计">
                  2k
                </span>
              

              
                <span class="post-meta-divider">|</span>
              

              
                <span class="post-meta-item-icon">
                  <i class="fa fa-clock-o"></i>
                </span>
                
                  <span class="post-meta-item-text">阅读时长 &asymp;</span>
                
                <span title="阅读时长">
                  8
                </span>
              
            </div>
          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>前段时间搞 LR 的特征优化，切身体会到人工特征工程实在太费劲了，一方面发掘高价值的特征十分困难，另一方面某些特征之间需要组合才能有效，比如用户对视频的某个特征的偏好，就必须将视频的特征和用户的特征进行组合。LR 是线性模型，没法自动做特征组合，只能人工搞，但人工来干这事就相当麻烦了。自然而然的，就会想到用可以自动组合特征的模型。现在了解的包括 FM、FFM 等基于矩阵分解的模型、基于 GBDT 之类的树模型和基于 DNN 的网络模型。这篇文章先介绍下 FFM 模型。</p>
<h2 id="FFM-模型简介"><a href="#FFM-模型简介" class="headerlink" title="FFM 模型简介"></a>FFM 模型简介</h2><p>FFM (Field-aware Factorization Machines)$^{[1]}$是 Yuchin Juan 等人在台大期间提出的用于 CTR 预估的模型。它是对 FM 模型的推广，提到 FM 又不得不提到 Poly2 模型，好在它们三个的关系十分简单和明确：</p>
<ol>
<li><p>Poly2 模型是将所有特征进行两两组合，也就是当特征有 $n$ 个的时候，需要 $O(n^2)$ 个参数，而且这些参数之间是<strong>相互独立</strong>的，意味着<strong>每个参数都需要足够的样本来训练</strong>，也就是每对特征都同时出现在足够多的样本里。因此如果无法满足海量样本的要求时，这个模型很难训练出来。它的模型如下（其中 $h(i,j)$ 作用是将 $i,j$ 映射成一个自然数）：</p>
<script type="math/tex; mode=display">
\phi_{poly2}(\mathcal{w},\mathcal{x}) = \sum_{j_1=1}^n\sum_{j_2=j_1+1}^n w_{h(j_1,j_2)}x_{j_1}x_{j_2} \qquad (1)</script></li>
<li><p>FM 模型是为每个特征训练一个隐向量，而特征组合的权重就是这两个特征的隐向量点积，假设隐向量的长度为 $k$，那么需要 $O(nk)$ 个参数，因此参数的规模要比 Poly2 小很多（这里可以认为 Poly2 为每个特征生成的向量长度为 $n$），训练数据量要求也就没那么高了。它的原始形态 (2) 和简化计算形态 (3) 分别如下：</p>
</li>
</ol>
<script type="math/tex; mode=display">
\phi_{FM}(\mathcal{w},\mathcal{x})= \sum_{j_1=1}^n\sum_{j_2=j_1+1}^n (\mathcal{w}_{j_1}\cdot\mathcal{w}_{j_2})x_{j_1}x_{j_2} \qquad (2)</script><script type="math/tex; mode=display">
\phi_{FM}(\mathcal{w},\mathcal{x})=\frac{1}{2}\sum_{j=1}^n(\mathcal{s}-\mathcal{w}_j x_j), \quad \mathcal{s}=\sum_{j'=1}^n\mathcal{w}_{j'} x_{j'} \qquad (3)</script><ol>
<li>FFM 模型是为每个特征对每一个 Field 学习一个隐向量，一个 Field 可以认为是特征所属的属性，比如用户的常驻地可以看成是一个 Field、视频的分类可以看成是另一个 Field，假设有 $f$ 个 Field，每个隐向量长度为 $k$，则FFM模型需要 $O(nfk)$ 个参数，看起来比 FM 多很多，但是实际上由于每个特征对不同 Field 的作用都是单独学习的，因此 FFM 的 $k$ 往往比 FM 的 $k$ 小很多。它的模型如下：</li>
</ol>
<script type="math/tex; mode=display">
\phi_{FFM}(\mathcal{w},\mathcal{x})= \sum_{j_1=1}^n\sum_{j_2=j_1+1}^n (\mathcal{w}_{j_1,f_2}\cdot\mathcal{w}_{j_2,f_1})x_{j_1}x_{j_2} \qquad (4)</script><p>FFM 为什么要把 Field 拎出来考虑呢？举个例子，还是在视频推荐里，假设只考虑用户的年龄特征、视频的分类特征和演员特征，FM 在学用户年龄特征的时候是综合考虑视频分类和演员来得到的，然而从直观上来看，年龄对分类的影响和对演员的影响是不同的，因此更自然的想法是对分类和演员各学一个隐向量，效果应该会更好。</p>
<p>换句话说，如果特征有明显的 Field 划分，用 FFM 模型理论上是优于 FM 的；但是如果不满足这个条件，例如在 NLP 领域，所有特征都属于一个 Field，FFM 模型的优势就不明显了。<br>另外，Field 很容易对应到一个类别，因此 FFM 特别适合处理类别特征，对于连续特征，如果离散化处理效果比较好也还OK，否则优势也不明显。<br>因此，<strong>FFM 主要适合处理类别特征，并且喜欢稀疏数据，而不适合处理连续特征，不适合处理 Field 数量很少的数据</strong>。</p>
<h2 id="FFM-模型实现"><a href="#FFM-模型实现" class="headerlink" title="FFM 模型实现"></a>FFM 模型实现</h2><p>由于官方只提供了 FFM 模型的 C++ 实现$^{[2]}$，而我们主要是基于 Spark 的，因此需要一份 scala 实现。网上也找了一下，发现 Vince Shieh 实现的一份代码$^{[3]}$，但是 review 以后发现参数有点问题，因此考虑自己实现一份。<br>实现的 FFM 的核心就在于如何计算梯度，如何更新模型。论文的模型 (4) 是简化处理，在实现的时候还需要带上全局偏置和线性部分，完整的模型如下：</p>
<script type="math/tex; mode=display">
\phi_{FFM}(\mathcal{w},\mathcal{x})= w_0 + \sum_{j=1}^n w_jx_j+ \sum_{j_1=1}^n\sum_{j_2=j_1+1}^n (\mathcal{w}_{j_1,f_2}\cdot\mathcal{w}_{j_2,f_1})x_{j_1}x_{j_2} \qquad (5)</script><p>而 FFM 用于 CTR 预估时，目标优化函数定义成：</p>
<script type="math/tex; mode=display">
\mathcal{L}=\min_{\mathcal{w}} \frac{\lambda}{2}||\mathcal{w}||^2_2+\sum_{i=1}^m \log(1+e^{-y_i\phi(\mathcal{w},\mathcal{x})}) \qquad (6)</script><p>使用 SGD 的方式进行更新，即每次使用一个样本 $(y,\mathcal{x})$ 来更新模型，其中，$\mathcal{x}$ 的格式为 <script type="math/tex">\mathcal{x}=[f_{i_1}j_{i_1}x_{i_1},\cdots,f_{i_t}j_{i_t}x_{i_t}]</script>，表示该样本中 $t$ 个非零特征，$f$ 表示特征的域编号，$j$ 表示特征编号，$x$ 表示特征取值（对于 one-hot 编码，$x=1$）。<br>首先对式 (6) 中各权重计算梯度：</p>
<script type="math/tex; mode=display">
\begin{cases}
g_0=\lambda w_0+\kappa \\
g_j=\lambda w_j+\kappa w_j \\
\mathcal{g}_{j_1,f_2}=\lambda \mathcal{w}_{j_1,f_2}+\kappa \mathcal{w}_{j_2,f_1} \\
\mathcal{g}_{j_2,f_1}=\lambda \mathcal{w}_{j_2,f_1}+\kappa \mathcal{w}_{j_1,f_2}
\end{cases}, 
\quad \kappa=\frac{-y_ie^{-y_i\phi(\mathcal{w},\mathcal{x})}}{1+e^{-y_i\phi(\mathcal{w},\mathcal{x})}} \qquad (7)</script><p>然后使用 AdaGrad 对累积梯度进行更新（这里也可以不用 AdaGrad，直接使用 GD，或者用 Adam 等其他方法更新）：</p>
<script type="math/tex; mode=display">
\begin{cases}
G_i=G_i+g_i^2 \\
w_i=w_i-\frac{\eta}{\sqrt{G_i}} g_i
\end{cases},
\quad i=0, i_1, \cdots, i_t \qquad (8)</script><script type="math/tex; mode=display">
\begin{cases}
(G_{j_1,f_2})_d=(G_{j_1,f_2})_d+(g_{j_1,f_2})_d^2 \\
(G_{j_2,f_1})_d=(G_{j_2,f_1})_d+(g_{j_2,f_1})_d^2 \\
(w_{j_1,f_2})_d=(w_{j_1,f_2})_d-\frac{\eta}{\sqrt{(G_{j_1,f_2})_d}} (g_{j_1,f_2})_d \\
(w_{j_2,f_1})_d=(w_{j_2,f_1})_d-\frac{\eta}{\sqrt{(G_{j_2,f_1})_d}} (g_{j_2,f_1})_d
\end{cases}, 
\quad d=1,\cdots, k,\qquad (9)</script><p>基于以上各式，可以很容易把算法写出来了：<br><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">Algorithm: Train FFM using SG</span><br><span class="line">  init G = ones(n,f,k)</span><br><span class="line">  init g = rand(n,f,k)[<span class="number">0</span>,<span class="number">1</span>/sqrt(k)]</span><br><span class="line">  <span class="keyword">for</span> epoch = <span class="number">1</span> to t:</span><br><span class="line">    <span class="keyword">for</span> i = <span class="number">1</span> to m:</span><br><span class="line">      sample a data point (y,x)</span><br><span class="line">      calculate kappa by (<span class="number">7</span>)</span><br><span class="line">      <span class="keyword">for</span> xi, xj <span class="keyword">in</span> x:</span><br><span class="line">        calculate gradients by (<span class="number">7</span>)</span><br><span class="line">        update weights by (<span class="number">8</span>)(<span class="number">9</span>)</span><br></pre></td></tr></table></figure></p>
<p>论文中指出，FFM 特别容易过拟合，其中，正则化系数 $\lambda$ 越小，效果越好但越容易过拟合；学习率 $\eta$ 越大，学习速度越快也越容易过拟合。我自己试了几个数据集，使用 $\lambda=0.00002,\ \eta=0.1,\ k=4$，一般 1~4 轮都差不多OK了，再多就容易过拟合。<br>为了防止过拟合，论文提出使用 <strong>early stopping</strong> 技术，即将训练数据进一步划分成训练集和验证集，每一轮用训练集更新完模型后，用验证集计算 logloss，并记录验证集 logloss 开始上升的轮数 $r$，最后再用整个数据集训练 $r$ 轮。但是实际在用的时候，可以线下调一个比较好的参数，然后直接放到线上去用，等数据发生变化，或者定时去重新评估这些参数。</p>
<p>自己用 scala 实现的 FFM 模型没有使用指令集加速，只是将训练数据划分成多个 partition 并行训练，然后将参数合并（求平均），效果差一些。我拿 libFFM 做了一个性能的比较……<strong>完败</strong>……唉，Spark 做数值计算还是不太行啊！</p>
<h2 id="References"><a href="#References" class="headerlink" title="References"></a>References</h2><p>[1] Juan, Yuchin, et al. “Field-aware Factorization Machines for CTR Prediction.” ACM Conference on Recommender Systems ACM, 2016:43-50.<br>[2] <a href="https://github.com/guestwalk/libffm" target="_blank" rel="noopener">https://github.com/guestwalk/libffm</a><br>[3] <a href="https://github.com/VinceShieh/spark-ffm" target="_blank" rel="noopener">https://github.com/VinceShieh/spark-ffm</a></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://guyuecanhui.gitee.io/hcigmoid/hcigmoid/2018/08/16/sub-modular/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="古月残辉">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/hcigmoid/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="HCigmoid">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hcigmoid/2018/08/16/sub-modular/" itemprop="url">Submodular函数</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2018-08-16T20:14:44+08:00">
                2018-08-16
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/hcigmoid/categories/数学/" itemprop="url" rel="index">
                    <span itemprop="name">数学</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/hcigmoid/2018/08/16/sub-modular/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/hcigmoid/2018/08/16/sub-modular/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          

          

          
            <div class="post-wordcount">
              
                
                <span class="post-meta-item-icon">
                  <i class="fa fa-file-word-o"></i>
                </span>
                
                  <span class="post-meta-item-text">字数统计&#58;</span>
                
                <span title="字数统计">
                  773
                </span>
              

              
                <span class="post-meta-divider">|</span>
              

              
                <span class="post-meta-item-icon">
                  <i class="fa fa-clock-o"></i>
                </span>
                
                  <span class="post-meta-item-text">阅读时长 &asymp;</span>
                
                <span title="阅读时长">
                  3
                </span>
              
            </div>
          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          <h2 id="Submodular-函数的定义与性质"><a href="#Submodular-函数的定义与性质" class="headerlink" title="Submodular 函数的定义与性质"></a>Submodular 函数的定义与性质</h2><p>最近在看一些计算学习理论的时候，发现很多文章是基于 <strong>Submodular</strong> 函数做的，就去了解了一下。<br>所谓 <strong>Submodular</strong> 函数，是指满足如下定义的<strong>集合函数</strong>$^{[1]}$：</p>
<blockquote>
<p>记 $[n]={1,2,\cdots,n}$ 为 Ground Set，记 $f:2^{[n]}\to\mathbb{R}$ 为一个集合函数，该函数是 submudular当：</p>
<script type="math/tex; mode=display">f(A)+f(B)\ge f(A\cup B)+f(A\cap B), \quad \forall A,B\subseteq[n] \qquad(1)</script></blockquote>
          <!--noindex-->
          <div class="post-button text-center">
            <a class="btn" href="/hcigmoid/2018/08/16/sub-modular/#more" rel="contents">
              阅读全文 &raquo;
            </a>
          </div>
          <!--/noindex-->
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://guyuecanhui.gitee.io/hcigmoid/hcigmoid/2018/08/16/sub-modular 2/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="古月残辉">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/hcigmoid/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="HCigmoid">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hcigmoid/2018/08/16/sub-modular 2/" itemprop="url">Submodular函数</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2018-08-16T20:14:44+08:00">
                2018-08-16
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/hcigmoid/categories/数学/" itemprop="url" rel="index">
                    <span itemprop="name">数学</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/hcigmoid/2018/08/16/sub-modular 2/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/hcigmoid/2018/08/16/sub-modular 2/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          

          

          
            <div class="post-wordcount">
              
                
                <span class="post-meta-item-icon">
                  <i class="fa fa-file-word-o"></i>
                </span>
                
                  <span class="post-meta-item-text">字数统计&#58;</span>
                
                <span title="字数统计">
                  773
                </span>
              

              
                <span class="post-meta-divider">|</span>
              

              
                <span class="post-meta-item-icon">
                  <i class="fa fa-clock-o"></i>
                </span>
                
                  <span class="post-meta-item-text">阅读时长 &asymp;</span>
                
                <span title="阅读时长">
                  3
                </span>
              
            </div>
          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <h2 id="Submodular-函数的定义与性质"><a href="#Submodular-函数的定义与性质" class="headerlink" title="Submodular 函数的定义与性质"></a>Submodular 函数的定义与性质</h2><p>最近在看一些计算学习理论的时候，发现很多文章是基于 <strong>Submodular</strong> 函数做的，就去了解了一下。<br>所谓 <strong>Submodular</strong> 函数，是指满足如下定义的<strong>集合函数</strong>$^{[1]}$：</p>
<blockquote>
<p>记 $[n]={1,2,\cdots,n}$ 为 Ground Set，记 $f:2^{[n]}\to\mathbb{R}$ 为一个集合函数，该函数是 submudular当：</p>
<script type="math/tex; mode=display">f(A)+f(B)\ge f(A\cup B)+f(A\cap B), \quad \forall A,B\subseteq[n] \qquad(1)</script></blockquote>
<p>它是对 <strong>Modular</strong> 函数的条件进行放松，而 <strong>Modular</strong> 函数是指满足如下定义的函数：</p>
<script type="math/tex; mode=display">
f(A)+f(B)=f(A\cup B)+f(A\cap B), \quad \forall A,B\subseteq[n] \qquad(2)</script><p>看定义，<strong>Submodular</strong> 函数与凹函数有些相似，不同的在于它并不限定元素的顺序！<br><strong>Submodular</strong> 函数还有一种等价式，更能体现它的一个核心特点：</p>
<script type="math/tex; mode=display">
f(A\cup \{i\})-f(A)\ge f(B\cup \{i\})-f(B), \quad \forall A\subseteq B\subseteq [n],\ i\not \in B \qquad(3)</script><p>通俗的来讲，这个特点就是<strong>边际效用递减</strong>，即增加一个元素对整体的收益贡献递减。这种边际效用递减的程度可以用曲率 $\kappa$（Curvature）来度量：$f_S(i)\ge (1-\kappa)f(i)$，其中，$0\le\kappa\le1$。</p>
<p>举两个跟推荐有关系的 <strong>Submodular</strong> 函数的例子：</p>
<ol>
<li><strong>视频推荐多样性：</strong>对于一个可推荐的视频集合 $S$，假设每个视频有一个分类 $g_i$，则一个推荐列表中不同类别的总数 $f(S)=\sum_i \mathbb{I}(g_i)$ 就是一个 <strong>Submodular</strong> 函数，其中，$\mathbb{I}(x)$ 表示元素 $x$ 是否存在。</li>
<li><strong>商品推广用户选择：</strong>对于一个社交网络的用户集合 $S$，如果某用户看过一个物品，则他有可能向他的朋友推荐和分享。假设某个物品在推广期时给 $k$ 个用户 $S_k$ 展示了，则最终该物品会展示给多少用户 $m=f(S_k)$ 是一个 <strong>Submodular</strong> 函数。</li>
</ol>
<p>最后简单介绍下它的一些性质。<strong>Submodular</strong> 函数首先是集合函数，因此满足如下性质：</p>
<ul>
<li><strong>非负性：</strong>$f(A)\ge 0$</li>
<li><strong>单调性：</strong>可以是单调增或单调减</li>
<li><strong>正则化：</strong>$f(\phi)=0$</li>
</ul>
<p>另外，根据定义，可以证明它还满足：</p>
<ul>
<li>若 $f_1,f_2,\cdots,f_k$ 是 <strong>Submodular</strong> 函数，给定 $w_1,w_2,\cdots,w_k\ge 0$，则 $g(S)=\sum_iw_if_i(S)$ 也是 <strong>Submodular</strong> 函数</li>
<li>若 $f$ 在 $X$ 集合上是 <strong>Submodular</strong> 函数，给定 $T\subseteq X$ 则 $f(S\cup T)$、$f(S\cap T)$、$f(X\setminus S)$ 都是 <strong>Submodular</strong> 函数</li>
</ul>
<p>由于 <strong>Submodular</strong> 函数性质好、易证明，它在机器学习、博弈论等领域的理论研究方面获得了广泛的应用$^{[1,2]}$。特别的，文献$[1]$基于 <strong>Submodular</strong> 目标提出了 PMAC 理论，是对 PAC 理论的扩展；文献$[2]$基于 <strong>Submodular</strong> 函数提出一种 AdaptiveSampling 的算法，可以在理论保证的前提下，将样本数大大减少，这里就不展开了。</p>
<h2 id="Reference"><a href="#Reference" class="headerlink" title="Reference"></a>Reference</h2><p>[1] Balcan, Maria Florina, and N. J. A. Harvey. “Learning submodular functions.” ACM Symposium on Theory of Computing ACM, 2011:793-802.<br>[2] Balkanski, Eric and Singer, Yaron. “Approximation Guarantees for Adaptive Sampling.” Proceedings of the 35th International Conference on Machine Learning, 2018:393-402.</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://guyuecanhui.gitee.io/hcigmoid/hcigmoid/2018/07/20/currying 2/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="古月残辉">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/hcigmoid/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="HCigmoid">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hcigmoid/2018/07/20/currying 2/" itemprop="url">柯里化 (Currying) 及其应用</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2018-07-20T16:12:41+08:00">
                2018-07-20
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/hcigmoid/categories/编程/" itemprop="url" rel="index">
                    <span itemprop="name">编程</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/hcigmoid/2018/07/20/currying 2/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/hcigmoid/2018/07/20/currying 2/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          

          

          
            <div class="post-wordcount">
              
                
                <span class="post-meta-item-icon">
                  <i class="fa fa-file-word-o"></i>
                </span>
                
                  <span class="post-meta-item-text">字数统计&#58;</span>
                
                <span title="字数统计">
                  998
                </span>
              

              
                <span class="post-meta-divider">|</span>
              

              
                <span class="post-meta-item-icon">
                  <i class="fa fa-clock-o"></i>
                </span>
                
                  <span class="post-meta-item-text">阅读时长 &asymp;</span>
                
                <span title="阅读时长">
                  3
                </span>
              
            </div>
          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>柯里化（<strong>Currying</strong>，以逻辑学家 Haskell Brooks Curry 的名字命名）指的是将原来接受两个参数的函数变成新的接受一个参数的函数的过程。新的函数返回一个以原有第二个参数作为参数的函数。乍一看不容易理解，我们结合几个例子来看看，在 <strong>scala</strong> 中，<strong>currying</strong> 是什么样的，以及什么时候我们可以考虑使用它。</p>
<h3 id="样例一：加法"><a href="#样例一：加法" class="headerlink" title="样例一：加法"></a>样例一：加法</h3><p>从最简单的开始，我们看一下 <strong>currying</strong> 是怎么把一个接受两个参数的函数改造成每次只接受一个参数的函数：</p>
<figure class="highlight scala"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// uncurry</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">add1</span></span>(x: <span class="type">Int</span>, y: <span class="type">Int</span>): <span class="type">Int</span> = &#123;</span><br><span class="line">  x + y</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// shorthand</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">add2</span></span>(x: <span class="type">Int</span>)(y: <span class="type">Int</span>): <span class="type">Int</span> = &#123;</span><br><span class="line">  x + y</span><br><span class="line">&#125;</span><br><span class="line">add2(<span class="number">2</span>) _</span><br><span class="line">add2(<span class="number">2</span>)(<span class="number">3</span>)</span><br><span class="line"></span><br><span class="line"><span class="comment">// longhand</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">add3</span></span>(x: <span class="type">Int</span>): (<span class="type">Int</span> =&gt; <span class="type">Int</span>) = &#123;</span><br><span class="line">  (y: <span class="type">Int</span>) =&gt; &#123;</span><br><span class="line">    x + y</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br><span class="line">add3(<span class="number">2</span>)</span><br><span class="line">add3(<span class="number">2</span>)(<span class="number">5</span>)</span><br></pre></td></tr></table></figure>
<p><strong>输出结果：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">res0: Int =&gt; Int = $$Lambda$1120/855429058@4702faee</span><br><span class="line">res1: Int = 5</span><br><span class="line">res2: Int =&gt; Int = $$Lambda$1119/1771691170@f6b85c3</span><br><span class="line">res3: Int = 7</span><br></pre></td></tr></table></figure>
<p>从这里，我们可以看出，实际上 <code>add2(2)</code> 已经变成了一个 <strong>method</strong>，而 <code>add3(2)</code> 则变成了一个 <strong>function</strong>（<strong>method</strong> 和 <strong>function</strong> 的差别参考<a href="https://guyuecanhui.github.io/2018/07/17/method-vs-function/" target="_blank" rel="noopener">我之前的博客</a>），它们都可以将任何接受的参数加上 2 得到输出的结果。</p>
<h3 id="样例二：foldLeft"><a href="#样例二：foldLeft" class="headerlink" title="样例二：foldLeft"></a>样例二：foldLeft</h3><p>上面的例子实际上已经很清楚的说明了 <strong>currying</strong> 的特点，即固定一个参数作为函数的一部分，然后接受剩下的参数进行处理。下面这个例子是 <strong>scala</strong> 内置的代码 <code>foldLeft</code>，我们平时也经常会用到，它将对一个列表的操作转换成了依次对列表中每个元素的操作：</p>
<figure class="highlight scala"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">foldLeft</span></span>[<span class="type">B</span>](z: <span class="type">B</span>)(op: (<span class="type">B</span>, <span class="type">A</span>) =&gt; <span class="type">B</span>): <span class="type">B</span> = &#123;</span><br><span class="line">    <span class="keyword">var</span> acc = z</span><br><span class="line">    <span class="keyword">var</span> these = <span class="keyword">this</span></span><br><span class="line">    <span class="keyword">while</span> (!these.isEmpty) &#123;</span><br><span class="line">        acc = op(acc, these.head)</span><br><span class="line">        these = these.tail</span><br><span class="line">    &#125;</span><br><span class="line">    acc</span><br><span class="line">&#125;</span><br><span class="line"><span class="type">List</span>(<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>).foldLeft(<span class="string">"res:"</span>)((x: <span class="type">String</span>, y:<span class="type">Int</span>) =&gt; x + y)</span><br></pre></td></tr></table></figure>
<h4 id="输出结果："><a href="#输出结果：" class="headerlink" title="输出结果："></a>输出结果：</h4><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">res:123</span><br></pre></td></tr></table></figure>
<h3 id="样例三：人群分析报告"><a href="#样例三：人群分析报告" class="headerlink" title="样例三：人群分析报告"></a>样例三：人群分析报告</h3><p>最后，我们再举一个例子，尝试着说明一下在什么情况下可以考虑使用 <strong>currying</strong>。考虑我们有一个函数能够接受用户的各种属性和待分析的视频 ID，输出具备指定属性的用户对该视频的详细分析报告（好希望有），它的非 <strong>currying</strong> 形式如下：</p>
<figure class="highlight scala"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">godView</span></span>(age: <span class="type">String</span>, gender: <span class="type">String</span>, city: <span class="type">String</span>, netType: <span class="type">String</span>, videoID: <span class="type">String</span>): <span class="type">Unit</span> = &#123; <span class="comment">/** whoCanWhoUp **/</span> &#125;</span><br></pre></td></tr></table></figure>
<p>每天业务都会根据数据分析去定向 <strong>push</strong> 一些视频，但是有些 <strong>push</strong> 的效果不好，就需要分析为啥给某群用户推荐这个视频不好，我们借助这个 <code>godView</code> 函数来进行分析。假设我们有几个人被分到了不同的人群和一些视频列表，每个人都得仔细根据函数的输出的报告进行分析。比如我分到了使用 <strong>wifi</strong> 的中年上海男性，那我每次分析都需要把这些参数全都传进去：</p>
<figure class="highlight scala"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">godView(<span class="string">"35-45"</span>, <span class="string">"male"</span>, <span class="string">"shanghai"</span>, <span class="string">"wifi"</span>, <span class="string">"video1"</span>)</span><br><span class="line">godView(<span class="string">"35-45"</span>, <span class="string">"male"</span>, <span class="string">"shanghai"</span>, <span class="string">"wifi"</span>, <span class="string">"video2"</span>)</span><br><span class="line">godView(<span class="string">"35-45"</span>, <span class="string">"male"</span>, <span class="string">"shanghai"</span>, <span class="string">"wifi"</span>, <span class="string">"video3"</span>)</span><br><span class="line">...</span><br></pre></td></tr></table></figure>
<p>对于我来说，多希望不需要每次传这些相同的参数，让我专心分析视频 ID 就好了，那我就希望把这个函数改造一下：</p>
<figure class="highlight scala"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">godView</span></span>(age: <span class="type">String</span>)(gender: <span class="type">String</span>)(city: <span class="type">String</span>)(netType: <span class="type">String</span>)(videoID: <span class="type">String</span>): <span class="type">Unit</span> = &#123; <span class="comment">/** whoCanWhoUp **/</span> &#125;</span><br></pre></td></tr></table></figure>
<p>然后我只把我关注的人群提取出来，再进行分析，就简洁多了：</p>
<figure class="highlight scala"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">val</span> myView = godView(<span class="string">"35-45"</span>)(<span class="string">"male"</span>)(<span class="string">"shanghai"</span>)(<span class="string">"wifi"</span>) _</span><br><span class="line">myView(<span class="string">"video1"</span>)</span><br><span class="line">myView(<span class="string">"video2"</span>)</span><br><span class="line">myView(<span class="string">"video3"</span>)</span><br><span class="line">...</span><br></pre></td></tr></table></figure>
<h3 id="Take-aways"><a href="#Take-aways" class="headerlink" title="Take-aways"></a>Take-aways</h3><p>从以上三个例子中，我们可以窥见 <strong>currying</strong> 的几个特点：</p>
<ol>
<li><strong>Currying</strong> 是把接受多个参数的函数变换成接受一个单一参数的函数，并且返回接受余下的参数且返回结果的新函数的技术；</li>
<li><strong>Currying</strong> 其实只是复用代码的一种思路，它并非不可替代；</li>
<li>当你发现你要调用一个函数，并且调用参数都是一样的情况下，这个参数就可以进行 <strong>currying</strong>，以便更好的完成任务；</li>
<li><strong>Currying</strong> 允许你写出来的代码更干净、更有表达力。</li>
</ol>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://guyuecanhui.gitee.io/hcigmoid/hcigmoid/2018/07/20/currying/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="古月残辉">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/hcigmoid/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="HCigmoid">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hcigmoid/2018/07/20/currying/" itemprop="url">柯里化 (Currying) 及其应用</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2018-07-20T16:12:41+08:00">
                2018-07-20
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/hcigmoid/categories/编程/" itemprop="url" rel="index">
                    <span itemprop="name">编程</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/hcigmoid/2018/07/20/currying/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/hcigmoid/2018/07/20/currying/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          

          

          
            <div class="post-wordcount">
              
                
                <span class="post-meta-item-icon">
                  <i class="fa fa-file-word-o"></i>
                </span>
                
                  <span class="post-meta-item-text">字数统计&#58;</span>
                
                <span title="字数统计">
                  998
                </span>
              

              
                <span class="post-meta-divider">|</span>
              

              
                <span class="post-meta-item-icon">
                  <i class="fa fa-clock-o"></i>
                </span>
                
                  <span class="post-meta-item-text">阅读时长 &asymp;</span>
                
                <span title="阅读时长">
                  3
                </span>
              
            </div>
          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          <p>柯里化（<strong>Currying</strong>，以逻辑学家 Haskell Brooks Curry 的名字命名）指的是将原来接受两个参数的函数变成新的接受一个参数的函数的过程。新的函数返回一个以原有第二个参数作为参数的函数。乍一看不容易理解，我们结合几个例子来看看，在 <strong>scala</strong> 中，<strong>currying</strong> 是什么样的，以及什么时候我们可以考虑使用它。</p>
          <!--noindex-->
          <div class="post-button text-center">
            <a class="btn" href="/hcigmoid/2018/07/20/currying/#more" rel="contents">
              阅读全文 &raquo;
            </a>
          </div>
          <!--/noindex-->
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://guyuecanhui.gitee.io/hcigmoid/hcigmoid/2018/07/17/method-vs-function/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="古月残辉">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/hcigmoid/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="HCigmoid">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hcigmoid/2018/07/17/method-vs-function/" itemprop="url">Scala 中函数与方法的差别</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2018-07-17T16:01:05+08:00">
                2018-07-17
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/hcigmoid/categories/编程/" itemprop="url" rel="index">
                    <span itemprop="name">编程</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/hcigmoid/2018/07/17/method-vs-function/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/hcigmoid/2018/07/17/method-vs-function/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          

          

          
            <div class="post-wordcount">
              
                
                <span class="post-meta-item-icon">
                  <i class="fa fa-file-word-o"></i>
                </span>
                
                  <span class="post-meta-item-text">字数统计&#58;</span>
                
                <span title="字数统计">
                  1.1k
                </span>
              

              
                <span class="post-meta-divider">|</span>
              

              
                <span class="post-meta-item-icon">
                  <i class="fa fa-clock-o"></i>
                </span>
                
                  <span class="post-meta-item-text">阅读时长 &asymp;</span>
                
                <span title="阅读时长">
                  5
                </span>
              
            </div>
          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          <p>本文主要举例介绍 Scala 中函数与方法的差别。</p>
          <!--noindex-->
          <div class="post-button text-center">
            <a class="btn" href="/hcigmoid/2018/07/17/method-vs-function/#more" rel="contents">
              阅读全文 &raquo;
            </a>
          </div>
          <!--/noindex-->
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://guyuecanhui.gitee.io/hcigmoid/hcigmoid/2018/07/17/method-vs-function 2/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="古月残辉">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/hcigmoid/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="HCigmoid">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hcigmoid/2018/07/17/method-vs-function 2/" itemprop="url">Scala 中函数与方法的差别</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2018-07-17T16:01:05+08:00">
                2018-07-17
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/hcigmoid/categories/编程/" itemprop="url" rel="index">
                    <span itemprop="name">编程</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/hcigmoid/2018/07/17/method-vs-function 2/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/hcigmoid/2018/07/17/method-vs-function 2/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          

          

          
            <div class="post-wordcount">
              
                
                <span class="post-meta-item-icon">
                  <i class="fa fa-file-word-o"></i>
                </span>
                
                  <span class="post-meta-item-text">字数统计&#58;</span>
                
                <span title="字数统计">
                  1.1k
                </span>
              

              
                <span class="post-meta-divider">|</span>
              

              
                <span class="post-meta-item-icon">
                  <i class="fa fa-clock-o"></i>
                </span>
                
                  <span class="post-meta-item-text">阅读时长 &asymp;</span>
                
                <span title="阅读时长">
                  5
                </span>
              
            </div>
          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <h3 id="1-引子"><a href="#1-引子" class="headerlink" title="1. 引子"></a>1. 引子</h3><p>在 <strong>Spark</strong> 开发过程中，我们经常会定义一些 <code>udf</code> 函数，用于对 <strong>DataFrame</strong> 的列进行变换，例如：</p>
<figure class="highlight scala"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">val</span> thres = <span class="number">3.0</span></span><br><span class="line"><span class="keyword">val</span> log10Udf = udf &#123; x: <span class="type">Long</span> =&gt; math.min(math.log10(x + <span class="number">2.0</span>), thres) &#125;</span><br><span class="line">df.withColumn(<span class="string">"newColumn"</span>, log10Udf($<span class="string">"oldColumn"</span>)).show</span><br></pre></td></tr></table></figure>
<p>这里的 <code>log10Udf</code> 是个啥呢？我们去看 <code>udf</code> 的定义，会发现它返回的是一个 <code>UserDefinedFunction</code> 对象：</p>
<figure class="highlight scala"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">udf</span></span>[<span class="type">RT</span>: <span class="type">TypeTag</span>, <span class="type">A1</span>: <span class="type">TypeTag</span>](f: <span class="type">Function1</span>[<span class="type">A1</span>, <span class="type">RT</span>]): <span class="type">UserDefinedFunction</span> = &#123;</span><br><span class="line">    <span class="keyword">val</span> inputTypes = <span class="type">Try</span>(<span class="type">ScalaReflection</span>.schemaFor(typeTag[<span class="type">A1</span>]).dataType :: <span class="type">Nil</span>).toOption</span><br><span class="line">    <span class="type">UserDefinedFunction</span>(f, <span class="type">ScalaReflection</span>.schemaFor(typeTag[<span class="type">RT</span>]).dataType, inputTypes)</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>可以确认一下：</p>
<figure class="highlight scala"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">scala&gt; log10Udf.getClass</span><br><span class="line">res1: <span class="type">Class</span>[_ &lt;: org.apache.spark.sql.expressions.<span class="type">UserDefinedFunction</span>] = <span class="class"><span class="keyword">class</span> <span class="title">org</span>.<span class="title">apache</span>.<span class="title">spark</span>.<span class="title">sql</span>.<span class="title">expressions</span>.<span class="title">UserDefinedFunction</span></span></span><br><span class="line"><span class="class"></span></span><br><span class="line"><span class="class"><span class="title">scala&gt;</span> <span class="title">log10Udf</span>.<span class="title">isInstanceOf</span>[java.lang.<span class="type">Object</span>]</span></span><br><span class="line"><span class="class"><span class="title">res2</span></span>: <span class="type">Boolean</span> = <span class="literal">true</span></span><br></pre></td></tr></table></figure>
<p>这里就引出了一个小小的疑问，我们平时 <code>def</code> 的东西也是个对象吗？例如我们尝试一下：</p>
<figure class="highlight scala"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">scala&gt; <span class="function"><span class="keyword">def</span> <span class="title">inc</span></span>(x:<span class="type">Int</span>) = x + <span class="number">1</span></span><br><span class="line">inc: (x: <span class="type">Int</span>)<span class="type">Int</span></span><br><span class="line"></span><br><span class="line">scala&gt; inc.isInstanceOf[java.lang.<span class="type">Object</span>]</span><br><span class="line">&lt;console&gt;:<span class="number">13</span>: error: missing argument list <span class="keyword">for</span> method inc</span><br><span class="line"><span class="type">Unapplied</span> methods are only converted to functions when a function <span class="class"><span class="keyword">type</span> <span class="title">is</span> <span class="title">expected</span>.</span></span><br><span class="line"><span class="class"><span class="title">You</span> <span class="title">can</span> <span class="title">make</span> <span class="title">this</span> <span class="title">conversion</span> <span class="title">explicit</span> <span class="title">by</span> <span class="title">writing</span> `<span class="title">inc</span> <span class="title">_</span>` <span class="title">or</span> `<span class="title">inc</span>(<span class="params">_</span>)` <span class="title">instead</span> <span class="title">of</span> `<span class="title">inc</span>`.</span></span><br><span class="line"><span class="class">       <span class="title">inc</span>.<span class="title">isInstanceOf</span>[java.lang.<span class="type">Object</span>]</span></span><br><span class="line"><span class="class">       <span class="title">^</span></span></span><br></pre></td></tr></table></figure>
<p>从上面的报错信息我们可以分析出来两点：</p>
<ol>
<li><code>def</code> 的结果并不是一个对象，而是一个 <strong>method</strong>；</li>
<li>可以通过 <code>_</code> 操作符将一个 <strong>method</strong> 转成一个 <strong>function</strong>；</li>
</ol>
<p>确认一下：</p>
<figure class="highlight scala"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">scala&gt; (inc _).isInstanceOf[java.lang.<span class="type">Object</span>]</span><br><span class="line">res3: <span class="type">Boolean</span> = <span class="literal">true</span></span><br><span class="line"></span><br><span class="line">scala&gt; (inc _).getClass</span><br><span class="line">res4: <span class="type">Class</span>[_ &lt;: <span class="type">Int</span> =&gt; <span class="type">Int</span>] = <span class="class"><span class="keyword">class</span> <span class="title">$$Lambda$1421/1772552470</span></span></span><br></pre></td></tr></table></figure>
<h3 id="2-method-vs-function"><a href="#2-method-vs-function" class="headerlink" title="2. method vs. function"></a>2. method vs. function</h3><p>一个很自然的问题就提出来了：<strong>method</strong> 和 <strong>function</strong> 有啥差别呢？可以去<a href="https://docs.scala-lang.org/glossary/index.html" target="_blank" rel="noopener">官方文档</a>上查询关键字 function：</p>
<blockquote>
<p>A function can be invoked with a list of arguments to produce a result. A function has a parameter list, a body, and a result type. <strong>Functions that are members of a class, trait, or singleton object are called methods.</strong> Functions defined inside other functions are called local functions. Functions with the result type of Unit are called procedures. Anonymous functions in source code are called function literals. <strong>At run time, function literals are instantiated into objects called function values.</strong></p>
</blockquote>
<p>简单的来讲，<strong>method</strong> 是定义在 <code>class</code>, <code>trait</code> 或者 <code>object</code> 里的 <strong>function</strong>，而匿名函数（Anonymous functions）会在运行时被实例化成 <strong>object</strong>。所谓的匿名函数就是没有名字的函数（-_-!），例如：<code>(x: Int) =&gt; x + 2</code> 就是一个匿名函数，我们可以将它赋值给一个变量：</p>
<figure class="highlight scala"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">val</span> inc2 = (x: <span class="type">Int</span>) =&gt; x + <span class="number">2</span></span><br></pre></td></tr></table></figure>
<p>把它写到一个类定义里，再尝试着编译一下，会得到这个匿名函数的定义：</p>
<figure class="highlight scala"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">public <span class="keyword">final</span> <span class="class"><span class="keyword">class</span> <span class="title">test$$anonfun$1</span> <span class="keyword">extends</span> <span class="title">java</span>.<span class="title">lang</span>.<span class="title">Object</span> <span class="title">implements</span> <span class="title">scala</span>.<span class="title">Function1</span>,<span class="title">scala</span>.<span class="title">ScalaObject</span></span></span><br></pre></td></tr></table></figure>
<p>其中，值得关注的是这个匿名函数实现了 <strong>trait</strong> <code>scala.Function1</code>（实际上，<strong>scala</strong> 包里定义了 <code>Function0</code> ~ <code>Function22</code> 表示接受 0 ~ 22 个参数的函数），它的代码如下：</p>
<figure class="highlight scala"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">@annotation</span>.implicitNotFound(msg = <span class="string">"No implicit view available from $&#123;T1&#125; =&gt; $&#123;R&#125;."</span>)</span><br><span class="line"><span class="class"><span class="keyword">trait</span> <span class="title">Function1</span>[@specialized(scala.<span class="type">Int</span>, scala.<span class="type">Long</span>, scala.<span class="type">Float</span>, scala.<span class="type">Double</span>) -<span class="type">T1</span>, @specialized(scala.<span class="type">Unit</span>, scala.<span class="type">Boolean</span>, scala.<span class="type">Int</span>, scala.<span class="type">Float</span>, scala.<span class="type">Long</span>, scala.<span class="type">Double</span>) +<span class="type">R</span>] <span class="keyword">extends</span> <span class="title">AnyRef</span> </span>&#123; self =&gt;</span><br><span class="line">  <span class="comment">/** Apply the body of this function to the argument.</span></span><br><span class="line"><span class="comment">   *  @return   the result of function application.</span></span><br><span class="line"><span class="comment">   */</span></span><br><span class="line">  <span class="function"><span class="keyword">def</span> <span class="title">apply</span></span>(v1: <span class="type">T1</span>): <span class="type">R</span></span><br><span class="line">  <span class="meta">@annotation</span>.unspecialized <span class="function"><span class="keyword">def</span> <span class="title">compose</span></span>[<span class="type">A</span>](g: <span class="type">A</span> =&gt; <span class="type">T1</span>): <span class="type">A</span> =&gt; <span class="type">R</span> = &#123; x =&gt; apply(g(x)) &#125;</span><br><span class="line">  <span class="meta">@annotation</span>.unspecialized <span class="function"><span class="keyword">def</span> <span class="title">andThen</span></span>[<span class="type">A</span>](g: <span class="type">R</span> =&gt; <span class="type">A</span>): <span class="type">T1</span> =&gt; <span class="type">A</span> = &#123; x =&gt; g(apply(x)) &#125;</span><br><span class="line">  <span class="keyword">override</span> <span class="function"><span class="keyword">def</span> <span class="title">toString</span></span>() = <span class="string">"&lt;function1&gt;"</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>根据注释推测，这个匿名函数实际上就是定义了 <code>apply</code> 方法；当我们调用 <code>inc2(3)</code> 时，我们实际上是调用了这个对象的 <code>apply</code> 方法。确认一下：</p>
<figure class="highlight scala"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">val</span> inc2 = (x: <span class="type">Int</span>) =&gt; x + <span class="number">2</span></span><br><span class="line"><span class="keyword">val</span> anonfun = <span class="keyword">new</span> <span class="type">Function1</span>[<span class="type">Int</span>, <span class="type">Int</span>] &#123;</span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">apply</span></span>(x: <span class="type">Int</span>): <span class="type">Int</span> = x + <span class="number">2</span></span><br><span class="line">&#125;</span><br><span class="line">assert(inc2(<span class="number">0</span>) == anonfun(<span class="number">0</span>))</span><br></pre></td></tr></table></figure>
<p>嗯，终于理顺了 ~ 好了，我们再用这个例子串一下：</p>
<figure class="highlight scala"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line">scala&gt; <span class="function"><span class="keyword">def</span> <span class="title">inc</span></span>(x: <span class="type">Int</span>) = x + <span class="number">1</span></span><br><span class="line">inc: (x: <span class="type">Int</span>)<span class="type">Int</span></span><br><span class="line"></span><br><span class="line">scala&gt; <span class="keyword">val</span> inc2 = (x: <span class="type">Int</span>) =&gt; x + <span class="number">2</span></span><br><span class="line">inc2: <span class="type">Int</span> =&gt; <span class="type">Int</span> = $$<span class="type">Lambda</span>$<span class="number">1035</span>/<span class="number">948692477</span>@<span class="number">8</span>f2e3e6</span><br><span class="line"></span><br><span class="line">scala&gt; <span class="keyword">val</span> inc3 = inc _</span><br><span class="line">inc3: <span class="type">Int</span> =&gt; <span class="type">Int</span> = $$<span class="type">Lambda</span>$<span class="number">1042</span>/<span class="number">1739111611</span>@<span class="number">1</span>bb96449</span><br><span class="line"></span><br><span class="line">scala&gt; inc2.toString</span><br><span class="line">res0: <span class="type">String</span> = $$<span class="type">Lambda</span>$<span class="number">1035</span>/<span class="number">948692477</span>@<span class="number">8</span>f2e3e6</span><br><span class="line"></span><br><span class="line">scala&gt; inc.toString</span><br><span class="line">&lt;console&gt;:<span class="number">13</span>: error: missing argument list <span class="keyword">for</span> method inc</span><br><span class="line"><span class="type">Unapplied</span> methods are only converted to functions when a function <span class="class"><span class="keyword">type</span> <span class="title">is</span> <span class="title">expected</span>.</span></span><br><span class="line"><span class="class"><span class="title">You</span> <span class="title">can</span> <span class="title">make</span> <span class="title">this</span> <span class="title">conversion</span> <span class="title">explicit</span> <span class="title">by</span> <span class="title">writing</span> `<span class="title">inc</span> <span class="title">_</span>` <span class="title">or</span> `<span class="title">inc</span>(<span class="params">_</span>)` <span class="title">instead</span> <span class="title">of</span> `<span class="title">inc</span>`.</span></span><br><span class="line"><span class="class">       <span class="title">inc</span>.<span class="title">toString</span></span></span><br><span class="line"><span class="class">       <span class="title">^</span></span></span><br><span class="line"><span class="class"></span></span><br><span class="line"><span class="class"><span class="title">scala&gt;</span> <span class="title">val</span> <span class="title">inc4</span> </span>= inc</span><br><span class="line">&lt;console&gt;:<span class="number">12</span>: error: missing argument list <span class="keyword">for</span> method inc</span><br><span class="line"><span class="type">Unapplied</span> methods are only converted to functions when a function <span class="class"><span class="keyword">type</span> <span class="title">is</span> <span class="title">expected</span>.</span></span><br><span class="line"><span class="class"><span class="title">You</span> <span class="title">can</span> <span class="title">make</span> <span class="title">this</span> <span class="title">conversion</span> <span class="title">explicit</span> <span class="title">by</span> <span class="title">writing</span> `<span class="title">inc</span> <span class="title">_</span>` <span class="title">or</span> `<span class="title">inc</span>(<span class="params">_</span>)` <span class="title">instead</span> <span class="title">of</span> `<span class="title">inc</span>`.</span></span><br><span class="line"><span class="class">       <span class="title">val</span> <span class="title">inc4</span> </span>= inc</span><br><span class="line">                  ^</span><br></pre></td></tr></table></figure>
<h3 id="3-Take-aways"><a href="#3-Take-aways" class="headerlink" title="3. Take-aways"></a>3. Take-aways</h3><p>这篇短文主要比较了之前容易忽略的两个概念：<strong>method</strong> 和 <strong>function</strong> 的联系和细微的差别：</p>
<ol>
<li><strong>method</strong> 是定义在 <code>class</code>, <code>trait</code> 或者 <code>object</code> 里的 <strong>function</strong>；</li>
<li>在运行时，匿名函数会被实例化成 <strong>object</strong>，因此可以把匿名函数赋值给一个变量，调用匿名函数实际上是调用这个对象的 <code>apply</code> 方法；</li>
<li><strong>method</strong> 本身只是一段代码，并不会被实例化，也不能对它进行赋值等操作，但是 <strong>method</strong> 通过 <code>_</code> 操作符可以转换成一个 <strong>function</strong> 类型；</li>
</ol>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://guyuecanhui.gitee.io/hcigmoid/hcigmoid/2018/02/24/svdpp 2/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="古月残辉">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/hcigmoid/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="HCigmoid">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hcigmoid/2018/02/24/svdpp 2/" itemprop="url">SVD++ 论文精读</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2018-02-24T20:16:34+08:00">
                2018-02-24
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/hcigmoid/categories/论文精读/" itemprop="url" rel="index">
                    <span itemprop="name">论文精读</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/hcigmoid/2018/02/24/svdpp 2/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/hcigmoid/2018/02/24/svdpp 2/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          

          

          
            <div class="post-wordcount">
              
                
                <span class="post-meta-item-icon">
                  <i class="fa fa-file-word-o"></i>
                </span>
                
                  <span class="post-meta-item-text">字数统计&#58;</span>
                
                <span title="字数统计">
                  2.9k
                </span>
              

              
                <span class="post-meta-divider">|</span>
              

              
                <span class="post-meta-item-icon">
                  <i class="fa fa-clock-o"></i>
                </span>
                
                  <span class="post-meta-item-text">阅读时长 &asymp;</span>
                
                <span title="阅读时长">
                  12
                </span>
              
            </div>
          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <blockquote>
<p>论文引用：Koren, Y. . (2008). Factorization meets the neighborhood : a multifaceted collaborative filtering model. Proceedings of the 14th ACM SIGKDD International Conference of Knowledge Discovery and Data Mining, 2008. ACM Press.</p>
</blockquote>
<p>本文对协同过滤中最主要的两种方法（基于邻域的方法和基于隐特征模型的方法）分别提出了优化方案，并且设计了一个联合模型将两种方法统一，从而达到更好的效果。为了进行区分，本文将对 SVD 进行优化的方案称为 SVD+，将联合模型的方法称为 SVD++。</p>
<h1 id="研究背景"><a href="#研究背景" class="headerlink" title="研究背景"></a>研究背景</h1><p>Koren 在做 Netflix 的比赛过程中，发现基于邻域的方法和基于隐特征模型的方法各有所长：</p>
<div class="table-container">
<table>
<thead>
<tr>
<th>比较</th>
<th>基于邻域的方法</th>
<th>基于隐特征模型的方法</th>
</tr>
</thead>
<tbody>
<tr>
<td>主要思想</td>
<td>核心在于计算用户/物品的相似度，将相似用户的喜好推荐给用户，或将用户喜欢物品的相似仿物品推荐给用户</td>
<td>假设真正描述用户评分矩阵性质的内存特征（可能未知）其实只有少数几个，将用户和物品都映射到这些隐特征层，从而使得用户和物品直接关联起来</td>
</tr>
<tr>
<td>挖掘信息特征</td>
<td>能够对局部强相关的关系更敏感，而无法捕捉全局弱相关的关系</td>
<td>能够估计关联所有物品/用户的整体结构，但是难以反映局部强相关的关系</td>
</tr>
</tbody>
</table>
</div>
<p>因此，这两种方法存在天然的互补关系。另外，Koren 还发现，使用隐式反馈的数据能够提高推荐的准确性，而这两种方法都不支持使用隐式反馈的数据。基于这些发现，Koren 先分别将隐式反馈集成到两个模型中去，得到两个优化的模型，再提出一种联合模型，将这两个优化的模型进一步融合，从而得到更好的效果。</p>
<h1 id="模型推导"><a href="#模型推导" class="headerlink" title="模型推导"></a>模型推导</h1><p>文章从 Baseline 的模型，通过加入各种考虑因素，推导出基于邻域和基于隐特征的两个模型，再推导出联合模型。</p>
<h2 id="1、Baseline模型"><a href="#1、Baseline模型" class="headerlink" title="1、Baseline模型"></a>1、Baseline模型</h2><p>Baseline 模型就是基于历史数据的简单统计，主要看用户 $u$ 的平均评分 $b_u$、电影 $i$ 的平均评分 $b_i$ 和所有电影的平均评分 $\mu$：</p>
<script type="math/tex; mode=display">
b_{ui} = \mu + b_u + b_i</script><p>所有后面的模型都是对这个基准模型的修正。这个基准模型中的参数都是可以离线计算的，用的方法也是本文通用的参数估计方法，先定义损失函数 $l(P)$：</p>
<script type="math/tex; mode=display">
l(p_1,p_2,\cdots) = \sum_{(u,i)\in \kappa} (r_{ui} - \hat{r_{ui}})^2 + \lambda(\sum_{p_1} p_1^2 + \sum_{p_2} p_2^2 + \cdots)</script><p>其中，<script type="math/tex">P=\{p_1,p_2,\cdots\}</script> 表示待估计的参数，$\kappa$ 表示所有显式反馈的组合（即用户 $u$ 对物品 $i$ 进行过评分），<script type="math/tex">r_{ui}</script> 表示评分的实际值，<script type="math/tex">\hat{r_{ui}}</script> 表示评分的预测值，$\lambda$ 为超参，根据经验设置，然后求最小化 $l(P)$ 下各参数的值，通常使用最小二乘法，或者文中使用的梯度下降法（效率更高）。比如这个地方，参数就 $b_u$ 和 $b_i$，可以根据下式进行参数估计：</p>
<script type="math/tex; mode=display">
\min_{b_*}\sum_{(u,i)\in \kappa} (r_{ui} - \hat{r_{ui}})^2 + \lambda(\sum_{p_1} p_1^2 + \sum_{p_2} p_2^2 + \cdots)</script><h2 id="2、推广到基于邻域的模型"><a href="#2、推广到基于邻域的模型" class="headerlink" title="2、推广到基于邻域的模型"></a>2、推广到基于邻域的模型</h2><p>本文主要考虑 ItemCF，对于两个物品 $i$ 和 $j$，它们的相似性 <script type="math/tex">s_{ij}</script> 是基于 Pearson 相关系数 <script type="math/tex">\rho_{ij}</script> 计算得到：</p>
<script type="math/tex; mode=display">
s_{ij} = \frac{n_{ij}}{n_{ij}+\lambda_2}\rho_{ij}, \\ \rho_{ij}=\frac{E((x-\mu_x)(y-\mu_y))}{\sigma_x\sigma_y}</script><p>其中，$n_{ij}$ 表示同时对 $i$ 和 $j$ 进行评分的用户数，$\lambda_2$ 应该是防止 $i$ 和 $j$ 比较冷门的情况下，恰好有个别用户同时对它们进行了评分，这时候它们的相关性实际是看不出来的，属于偶然情况，通常 $\lambda_2=100$。之前的 ItemCF 进一步利用用户 $u$ 评过分的与 $i$ 最相关的 $k$ 个物品 $S^k(i;u)$ 来估计用户 $u$ 对 $i$ 的评分：</p>
<script type="math/tex; mode=display">
\hat{r_{ui}} = b_{ui} + \frac{\sum_{j\in S^k(i;u)} s_{ij}(r_{uj} - b_{uj})}{\sum_{j\in S^k(i;u)} s_{ij}}</script><p>但是如果 $u$ 没有对与 $i$ 相似的物品评过分，那上式就主要取决于 <script type="math/tex">b_{ui}</script> 了。为了解决这个小问题，有方案先计算插值权重 $\theta_{ij}^u$ 来取代实际的评分：</p>
<script type="math/tex; mode=display">
\hat{r_{ui}} = b_{ui} + \sum_{j\in S^k(i;u)} \theta_{ij}^u (r_{uj} - b_{uj})</script><p>但是以上模型都只考虑了用户 $u$，而对全局结构没有一个很好的理解，因此 Koren 提出不仅仅使用用户 $u$ 的对 $i$ 最相关的 $k$ 个物品的评分数据，而是使用所有 $u$ 的评分数据，因此引入一个参数 <script type="math/tex">\omega_{ij}</script> 来表示 $j$ 的评分对 $i$ 评分的影响，并且这个 $\omega_{ij}$ 是基于所有用户对 $i$ 和 $j$ 评分估计出来的：</p>
<script type="math/tex; mode=display">
\hat{r_{ui}} = b_{ui} + \sum_{j\in R(u)} (r_{uj} - b_{uj})\omega_{ij}</script><p>分析这个式子，当 $i$ 和 $j$ 越相关，说明 $j$ 对 $i$ 的影响越大，即 <script type="math/tex">w_{ij}</script> 越大，这时候如果 <script type="math/tex">(r_{uj} - b_{uj})</script> 较大，则估计的评分相对于 <script type="math/tex">b_{ui}</script> 的偏移也就越多；反之，当 <script type="math/tex">w_{ij}</script> 较小时，无论 $j$ 的评分如何都对偏移影响不大。</p>
<p>在此基础上，进一步引入隐式反馈的数据：</p>
<script type="math/tex; mode=display">
\hat{r_{ui}} = b_{ui} + \sum_{j\in R(u)} (r_{uj} - b_{uj})\omega_{ij} +\sum_{j\in N(u)} c_{ij}</script><p>其中，<script type="math/tex">c_{ij}</script> 表示隐式反馈对基准估计的偏移影响，当 $j$ 与 $i$ 的评分强相关时，$c_{ij}$ 较大。这个式子的主要问题是，它对重度用户的推荐和对轻度用户的推荐结果相差较大，因为重度用户的显式反馈和隐式反馈都很多，因此偏移项值较大。Koren 发现，做一下正则化以后，效果会更好：</p>
<script type="math/tex; mode=display">
\hat{r_{ui}} = b_{ui} + \mid R(u)\mid ^{-1/2}\sum_{j\in R(u)} (r_{uj} - b_{uj})\omega_{ij} +\mid N(u)\mid ^{-1/2}\sum_{j\in N(u)} c_{ij}</script><p>为了降低上式的计算复杂度，可以只考虑对 $i$ 影响最大的 $k$ 个物品，记 $R^k(i;u)=R(u)\cap S^k(i)$ 表示 $u$ 评分过的物品中属于 $i$ 最相似的 TopK 物品，类似的，记 $N^k(i;u)=N(u)\cap S^k(i)$，这两个集合的元素个数通常是小于 $k$ 的（而如果 $u$ 对至少 $k$ 个物品评过分的话，$\mid S^k(i;u)\mid = k$）。则最终的模型为：</p>
<script type="math/tex; mode=display">
\hat{r_{ui}} = b_{ui} + \mid R^k(i;u)\mid ^{-1/2}\sum_{j\in R(u)} (r_{uj} - b_{uj})\omega_{ij} +\mid N^k(i;u)\mid ^{-1/2}\sum_{j\in N(u)} c_{ij}</script><p>使用之前提到的最小化 <script type="math/tex">f(b_u, b_i, w_{ij}, c_{ij})</script> 的方法来估计这些参数的取值。记 <script type="math/tex">e_{ui}=r_{ui} - \hat{r_{ui}}</script>，则使用梯度下降法得到的迭代公式如下：</p>
<script type="math/tex; mode=display">
\begin{cases}
b_u \leftarrow b_u+\gamma\cdot (e_{ui} - \lambda_4\cdot b_u) \\
b_i \leftarrow b_i+\gamma\cdot (e_{ui} - \lambda_4\cdot b_i) \\
\omega_{ij} \leftarrow \omega_{ij} + \gamma\cdot(\mid R^k(i;u)\mid ^{-1/2}\cdot e_{ui}\cdot (r_{uj} - b_{uj})-\lambda_4\cdot \omega_{ij}), \forall j \in R^k(i;u) \\
c_{ij} \leftarrow c_{ij} + \gamma\cdot(\mid N^k(i;u)\mid ^{-1/2}\cdot e_{ui}-\lambda_4\cdot c_{ij}), \forall j \in N^k(i;u)
\end{cases}</script><p>对于 Netflix 数据集，Koren 推荐取 $\gamma=0.005$，$\lambda_4=0.002$，对所有数据集进行 15 轮训练。从实际效果来看 $k$ 越大，推荐的效果越好。这个模型的计算主要集中在参数训练上，一旦模型训练出来了，就可以快速的进行在线的预测。</p>
<h2 id="3、推广到基于隐特征的模型"><a href="#3、推广到基于隐特征的模型" class="headerlink" title="3、推广到基于隐特征的模型"></a>3、推广到基于隐特征的模型</h2><p>原始的 SVD 是将用户和物品映射到一个隐特征集合：</p>
<script type="math/tex; mode=display">
\hat{r_{ui}} = b_{ui} + p_u^T\cdot q_i</script><p>由于用户的规模通常远大于物品的规模，因此考虑用 $u$ 喜欢的物品来对 $u$ 进行建模，再加上隐式反馈的数据，可以得到 Asymmetric-SVD 模型：</p>
<script type="math/tex; mode=display">
\hat{r_{ui}} = b_{ui} + q_i^T(\mid R(u)\mid ^{-1/2}\sum_{j\in R(u)} (r_{uj} - b_{uj})x_j +\mid N(u)\mid ^{-1/2}\sum_{j\in N(u)} y_j)</script><p>其中，<script type="math/tex">x_j</script> 和 <script type="math/tex">y_j</script> 是用来控制显式反馈和隐式反馈重要性比例的参数。用最小化 <script type="math/tex">f(b_u,b_i,q_i,x_j,y_j)</script> 来估计这些参数值。由于这里用 <script type="math/tex">(r_{uj} - b_{uj})x_j</script> 来替代原来的用户隐特征，因此数据量少了很多。该模型具有比较好的可解释性，并且对于新用户来讲，只要他做了一些反馈，即更新了 <script type="math/tex">r_{uj}</script> 后，就可以立即算出估计值；但是如果新上线一个物品，由于 <script type="math/tex">q_i^T</script> 需要重新估计，因此对新物品的冷启动需要一定的反应时间。</p>
<p>如果对于计算不是很 care 的话，当然可以不用这种简化处理，还是对用户直接进行建模（$p_u$），这样的效果会更好一些，但是可解释性之类的就要差一些：</p>
<script type="math/tex; mode=display">
\hat{r_{ui}} = b_{ui} + q_i^T(p_u +\mid N(u)\mid ^{-1/2}\sum_{j\in N(u)} y_j)</script><h2 id="4、联合模型"><a href="#4、联合模型" class="headerlink" title="4、联合模型"></a>4、联合模型</h2><p>如果把上面两个模型看成是 <code>预测值=基准估计+偏移量</code> 的话，那么这两个模型就可以混合到一起，变成：</p>
<script type="math/tex; mode=display">
\begin{align}
\hat{r_{ui}} &= b_{ui} \\
&+ q_i^T(p_u +\mid N(u)\mid ^{-1/2}\sum_{j\in N(u)} y_j) \\
&+ \mid R^k(i;u)\mid ^{-1/2}\sum_{j\in R(u)} (r_{uj} - b_{uj})\omega_{ij} +\mid N^k(i;u)\mid ^{-1/2}\sum_{j\in N(u)} c_{ij}
\end{align}</script><p>其中，第一项为基准估计，第二项 provides the interaction between the user profile and the item profile. In our example, it may find that “The Sixth Sense” and Joe are rated high on the Psychological Thrillers scale. 第三项 contributes fine grained adjustments that are hard to profile, such as the fact that Joe rated low the related movie “Signs”.</p>
<p>使用梯度下降法得到的迭代公式如下：</p>
<script type="math/tex; mode=display">
\begin{cases}
b_u \leftarrow b_u+\gamma_1\cdot (e_{ui} - \lambda_6\cdot b_u) \\
b_i \leftarrow b_i+\gamma_1\cdot (e_{ui} - \lambda_6\cdot b_i) \\
q_i \leftarrow q_i+ \gamma_2\cdot(e_{ui}\cdot(p_u+\mid N(u)\mid ^{-1/2}\sum_{j\in N(u)} y_j)-\lambda_7\cdot q_i) \\
p_u \leftarrow p_u + \gamma_2\cdot(e_{ui}\cdot q_i - \lambda_7\cdot p_u) \\
y_j \leftarrow y_j+\gamma_2\cdot(e_{ui} \cdot\mid N(u)\mid ^{-1/2} \cdot q_i - \lambda_7\cdot y_j) \\
\omega_{ij} \leftarrow \omega_{ij} + \gamma_3\cdot(\mid R^k(i;u)\mid ^{-1/2}\cdot e_{ui}\cdot (r_{uj} - b_{uj})-\lambda_8\cdot \omega_{ij}),\ \forall j \in R^k(i;u) \\
c_{ij} \leftarrow c_{ij} + \gamma_3\cdot(\mid N^k(i;u)\mid ^{-1/2}\cdot e_{ui}-\lambda_8\cdot c_{ij}),\ \forall j \in N^k(i;u)
\end{cases}</script><p>在 Netflix 的数据集上，建议参数为 <script type="math/tex">\gamma_1=\gamma_2=0.007</script>，<script type="math/tex">\gamma_3=0.001</script>，<script type="math/tex">\lambda_6=0.005</script>，<script type="math/tex">\lambda_7=\lambda_8=0.015</script>，整体迭代约 30 轮收敛，每一轮训练时，可以将 <script type="math/tex">\gamma_*</script> 减少 10%。而 $k=300$，再大也不会有明显的性能提升。</p>
<p>最后，Koren 还设计了一个比较巧妙的实验，解答了我一直以来一个疑问：RMSE 的提升是否也意味着推荐效果的提升。他们设计了一个针对 TopN 推荐的测试，主要的思想是先找出所有 5-star 的评分，认为这些评分意味着该用户喜欢这部电影，然后对所有这些 $(u,i)$，随机再选 1000 部电影，估计 $u$ 对这些电影的评分，看用户对这些电影里所有的 5-star 电影排名情况，然后对不同的算法进行比较，发现 RMSE 越小的算法，将 5-star 排到前面的概率也越大，从而说明了在这种情况下，RMSE 的提升也意味着推荐效果的提升。</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
  </section>

  
  <nav class="pagination">
    <a class="extend prev" rel="prev" href="/hcigmoid/page/5/"><i class="fa fa-angle-left"></i></a><a class="page-number" href="/hcigmoid/">1</a><span class="space">&hellip;</span><a class="page-number" href="/hcigmoid/page/5/">5</a><span class="page-number current">6</span><a class="page-number" href="/hcigmoid/page/7/">7</a><a class="extend next" rel="next" href="/hcigmoid/page/7/"><i class="fa fa-angle-right"></i></a>
  </nav>



          </div>
          


          

        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      

      <section class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <p class="site-author-name" itemprop="name">古月残辉</p>
              <p class="site-description motion-element" itemprop="description">总结心得</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/hcigmoid/archives/">
              
                  <span class="site-state-item-count">63</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/hcigmoid/categories/index.html">
                  <span class="site-state-item-count">6</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/hcigmoid/tags/index.html">
                  <span class="site-state-item-count">73</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          
            <div class="feed-link motion-element">
              <a href="/hcigmoid/atom.xml" rel="alternate">
                <i class="fa fa-rss"></i>
                RSS
              </a>
            </div>
          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="mailto:guyuecanhui@icloud.com" target="_blank" title="E-Mail">
                      
                        <i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                  </span>
                
            </div>
          

          
          

          
          

          

        </div>
      </section>

      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2018 &mdash; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">古月残辉</span>

  
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-area-chart"></i>
    </span>
    
      <span class="post-meta-item-text">Site words total count&#58;</span>
    
    <span title="Site words total count">109.2k</span>
  
</div>









<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>

        
<div class="busuanzi-count">
  <script async src="https://dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script>

  
    <span class="site-uv">
      <i class="fa fa-user"></i> 访问人数
      <span class="busuanzi-value" id="busuanzi_value_site_uv"></span>
      人
    </span>
  

  
    <span class="site-pv">
      <i class="fa fa-eye"></i> 总访问量
      <span class="busuanzi-value" id="busuanzi_value_site_pv"></span>
      次
    </span>
  
</div>








        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/hcigmoid/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/hcigmoid/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/hcigmoid/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/hcigmoid/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/hcigmoid/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/hcigmoid/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/hcigmoid/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/hcigmoid/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/hcigmoid/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/hcigmoid/js/src/schemes/pisces.js?v=5.1.4"></script>



  

  


  <script type="text/javascript" src="/hcigmoid/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  










  <script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
  <script src="//unpkg.com/valine/dist/Valine.min.js"></script>
  
  <script type="text/javascript">
    var GUEST = ['nick','mail','link'];
    var guest = 'nick,mail,link';
    guest = guest.split(',').filter(item=>{
      return GUEST.indexOf(item)>-1;
    });
    new Valine({
        el: '#comments' ,
        verify: false,
        notify: false,
        appId: '6du4Ppc2TvUuhcccRHSDNH2v-gzGzoHsz',
        appKey: 'zOKNml4W1Bq3OTzEuLt5hUjI',
        placeholder: '感谢阅读！欢迎评论！',
        avatar:'mm',
        guest_info:guest,
        pageSize:'10' || 10,
    });
  </script>



  

  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/hcigmoid/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'auto') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script>





  

  

  

  
  

  
  
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="//cdn.bootcss.com/mathjax/2.7.1/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
  


  

  

</body>
</html>
